#pragma once
#include <vector>
#include <cstring>
#include <string>

class TNode;
class Node;
class BfsNode;

/**
 * Node 索引树
 */
class Tree {
public:
	Tree(int dep);
	// 寻找 Node 但不创建 TNode 与 Node 节点
	Node* findNodeNoCreate(const std::string s);
	// 寻找 Tree 中的叶节点
	TNode* findTNode(const std::string s, const int dep);
	// 根据索引树找到 Node 但并不创建 Node
	Node** findNode(const std::string s);

private:
	TNode *root;
	int dep;
};

/**
 * De Brujin 图节点
 */
class Node {
public:
	Node(): next(NULL), id(0), maxDepthNode(-1), count(0), dep(0) {}
	Node(long long id): next(NULL), id(id), maxDepthNode(-1), count(0), dep(0) {}
	std::string toString();

	// next idx 都是索引树中的叶节点
	TNode *next;
	TNode *idx;
	long long id;
	long long maxDepthNode;
	long count;
	long dep;

};

/**
 * Node 树状索引节点
 * ch:
 *  * 叶节点时为 Node *
 *  * 非叶节点为 TNode *
 */
class TNode {
public:
	TNode(): f(NULL) {
		memset(ch, 0, sizeof(ch));
	}

	void *ch[4];
	TNode *f;
};

/**
 * 图中的路径
 */
class Path {
public:
	Path(): head(NULL), tail(NULL) {}
	std::string toString();
	size_t length() { return edges.length() + 1; }

	Node *head, *tail;
	// edges 中每个 char 为 0-3 表示核苷酸 id
	std::string edges;
};

/**
 * De Brujin 图
 */
class Graph {
public:
	Graph(int dep = 25) {
		this->dep = dep;
		t = new Tree(dep);
	}
	void readDataset(std::vector<std::string> dt);
	void readSeq(std::string seq);
	Node* addNode(std::string seq);
	Node* addNode(Node *node, char c);
	void deleteNode(Node *node);
	Path findLongestPath();
	// 寻找以 node 为起点的最长路径
	Path findPath(Node *node);
	void deletePath(Path *path);
	void reset();
	void clearBfs(bool clearVisit);
	// 删除权重小于 threshold 的节点
	void filter(int threshold);
	void clearVisit();

	Tree *t;
	std::vector<Node*> list; // id -> Node
	std::vector<BfsNode*> bfs;
	std::vector<bool> visit;
	// count: 节点数量
	// visitNum: 访问节点数量
	long count, visitNum;
	int dep, pathThreshold;
};

/**
 * 广度优先搜索节点
 */
class BfsNode {
public:
	BfsNode(): f(NULL), node(NULL), dep(0), edge(0) {}

	BfsNode *f;
	Node *node;
	long dep;
	int edge;
};
